ON SIMULTANEOUS OPTIMIZATION OF FORMULAS BY COMPLEXITY AND DELAY IN A MODEL WITH INTERGATE AND GATE’S INPUTS DELAYS

Danilov Boris Radislavovich, Research assistant, Lomonosov Moscow State University (1 Leninskie gory street, Moscow, Russia), brdanilov@gmail.com

519.714

Background. The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general, it consists in construction of the optimal (in a varying sense) structural implementation of the given discrete function in the given class of control systems. The theoretical results, obtained while solving the mentioned problem, find their applications in different applied areas, among which are the problems of integral circuits design. The traditional synthesis problem, according to its formulation in this particular work, concerns the study of the Shannon function for delay, i.e. the delay of the “worst” Boolean function that depends on the given set of n variables. The problem under investigation also includes a number of classic results in the theory of discrete control systems, concerning construction of circuits that are asymptotically optimal according to several parameters simultaneously. The goal of the work is to transfer the known results in the area of circuit synthesis, associated with simultaneous optimization of circuits by several parameters, over to circuit models that reflect capacitive peculiarity of gate interconnections with greater accuracy and also reflect timing parameters of gates under different input signals. The work considers a delay model over an arbitrary finite complete basis, where the gate delay (a positive real quantity) over any of its inputs depend on signals passed on its other inputs and is composed of two components: the gates interconnection delay of the input with the output of the previous gate, and the inner delay of the gate. Meanwhile, delays of a gate over its different inputs are, generally speaking, considered to be independent values.
Materials and methods. The instruments used in the research included a technique of universal sets of Boolean functions and a technique of Boolean functions modelling on components of Boolean cube special partitions. The synthesis method of formula type circuits that are asymptotically optimal both by complexity and by delay was implemented for circuit synthesis in the described delay model.
Results. The author obtained Shannon function asymptotics, linear in regard to n, for the delay of Boolean functions that depend on the given n variables. It turns out that incorporation of an additional delay component, such as its input signals dependence, doesn’t lead to a change of Shannon function asymptotical behavior. Formula type circuits, asymptotically optimal both by complexity and by delay, were constructed.
Conclusions. The established results allow to educe the applicability of the earlier known results, concerning simultaneous formula type circuits optimization by several parameters to a wider class of delay models.

complexity, delay, depth, function element circuits, multiplexor function.

1. Lozhkin S. A., Danilov B. R. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2013, no. 4, pp. 25–33.
2. Danilov B. R. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2014, no. 3 ( 31), pp. 78–100.
3. Lupanov O. B. Problemy kibernetiki [Problems of cybernetics]. Issue 23. Moscow: Nauka, 1970, pp. 43–82.
4. Lozhkin S. A. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. Issue 6. Moscow: Nauka, 1996, pp. 189–214.
5. Lozhkin S. A. Vestnik Moskovskogo universiteta. Ser. Matematika. Mekhanika [Bulletin Moscow University. Series: Mathematics. Mechanics]. 1996, no. 2, pp. 80–82.
6. Lozhkin S. A. Osnovy kibernetiki [Fundamentals of cybernetics].Moscow:Izd.otdel f-ta VMiK MGU,2004,251p.
7. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku: ucheb. posobie dlya vuzov [Introduction into discrete mathematics: tutorial for universities]. 4th ed. Moscow: Vysshaya shkola, 2003, 384 p.
8. Danilov B. R. Materialy X molodezhnoy nauchnoy shkoly po diskretnoy matematike i ee prilozheniyam (Moskva, 6–8 oktyabrya 2015 g.) [Proceedings of X youth scientific school on discrete mathematics and application thereof (Moscow, 6–8 October 2015)]. Moscow: IPM im. M. V. Keldysha, 2015, pp. 18–23.
9. Lozhkin S. A., Danilov B. R. Prikladnaya matematika i informatika [Applied mathematics and informatics]. 2011, no. 39, pp. 107–129.